#include <iostream>
#include <algorithm>
using namespace std;

struct data { int x, y; };

int const maxn = 1001;
int const maxp = 10001;
int d[maxn*2];
data da[maxp];
int n, p;

int main()
{
	cin >> n >> p;
	for (int i = 0; i < p; i++) cin >> da[i].x >> da[i].y;

	//break_point
	int ans = n;
	for (int b = 0; b < n; b++) {
		fill(d, d+2*n, -1);
		for (int i = 0; i < p; i++) {
			int u = da[i].x - 1; int v = da[i].y - 1;
			if (u <= b) u += n; if (v <= b) v += n;
			if (u > v) swap(u, v);
			d[u]= max(d[u], max(v, d[v]));
		}

		int tmp = 0, right = -1;
		for (int i = b+1; i < b+n+1; i++) {
			if (right == i) right = -1;
			if (right == -1 && d[i] == -1) tmp++;
			if (d[i] != -1) right = max(right, d[i]);
		}
		tmp = n-tmp;
		if (tmp < ans) ans = tmp;
	}
	cout << ans << "\n";
}

